
//2861.最大合金数
class Solution {
    typedef long long LL;
public:
    int maxNumberOfAlloys(int n, int k, int budget, vector<vector<int>>& composition, vector<int>& stock, vector<int>& cost) {
        
        //判断能否创建ret个合金
        auto check=[&](LL ret)
        {
            for(auto& nums:composition)
            {
                LL sum=0;
                for(int i=0;i<n;i++)
                    sum+=cost[i]*max(ret*nums[i]-stock[i],(LL)0);

                if(sum<=budget) return true;
            }
            return false;
        };

        int left=0,right=1e8*2+1;  //注意此处上界的取值：及要靠你budegt好要考虑stock
        while(left+1<right)
        {
            int mid=left+(right-left)/2;
            if(check(mid)) left=mid;
            else right=mid;
        }
        return left;
    }
};